#!/usr/bin/python
# -*- coding: utf8 -*-

def square(m):
    """ 求矩阵m的平方 """
    r2 = m[2]*m[2]+m[1]*m[1]
    r1 = m[2]*m[1]+m[1]*m[0]
    r0 = m[1]*m[1]+m[0]*m[0]
    m[2] = r2
    m[1] = r1
    m[0] = r0

def recur(matrix,n):
    # 递归结束条件
    if n == 1:
        return matrix
    else:
        recur(matrix,n/2)   # Divide and Conquer
        # Combine
        square(matrix)
        if(n % 2 == 1):     # 处理n为奇数的情况
            matrix[0] = matrix[1]
            matrix[1] = matrix[2]
            matrix[2] = matrix[0] + matrix[1]

def fib(n):
    """ Matrix """
    # 特殊情况：n=0,1,2
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        # matrix[0]为F(n-1),matrix[1]为F(n),matrix[2]为F(n+1)
        matrix = [0,1,1]
        recur(matrix,n)
        return matrix[1]

if __name__ == '__main__':
    print fib(30)
